package com.cat.dataStructure03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/most-profitable-path-in-a-tree/
 * @create 2025/11/17 10:33
 * @since JDK17
 */

public class Solution76 {
    List<Integer>[] g;
    int[] bobTime, amount;
    boolean dfsBob(int x, int t, int fa) {
        if (x == 0) {
            bobTime[x] = t;
            return true;
        }
        boolean found = false;
        for (int y : g[x]) {
            if (y != fa) {
                if (dfsBob(y, t + 1, x)) {
                    found = true;
                }
            }
        }
        if (found) {
            bobTime[x] = t;
        }
        return found;
    }
    int dfsAlice(int x, int t, int fa) {
        int ans = bobTime[x] < t ? 0 : bobTime[x] == t ? amount[x] / 2 : amount[x], res = Integer.MIN_VALUE;
        for (var y : g[x]) {
            if (y != fa) {
                res = Math.max(res, dfsAlice(y, t + 1, x));
            }
        }

        return ans + (res == Integer.MIN_VALUE ? 0 : res);
    }

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = amount.length;
        g = new List[n];
        Arrays.setAll(g, x -> new ArrayList<>());
        for (var e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        this.amount = amount;
        bobTime = new int[n];
        Arrays.fill(bobTime, Integer.MAX_VALUE);
        dfsBob(bob, 0, -1);
        return dfsAlice(0, 0, -1);
    }
}
